package newcoder.JZ46;

//31717126241541717
public class Solution {

    public static void main(String[] args) {
        String s = "72416145196211821232022471311148103136128331523141061051992231223";
        String s2 = "81031";
        String s3 = "810";
        System.out.println(solve(s));
    }

    public static int solve(String nums) {
        // write code here
        char[] chars = nums.toCharArray();
        if (chars.length == 1) {
            if (chars[0] >= '1' && chars[0] <= '9') {
                return 1;
            }
            return 0;
        }
        int[] d = new int[nums.length()];
        d[0] = 1;
        if (chars[1] == '0') {
            d[1] = 1;
        } else if (chars[0] < '2') {
            d[1] = 2;
        } else if (chars[0] == '2') {
            if (chars[1] <= '6') {
                d[1] = 2;
            } else {
                d[1] = 1;
            }
        } else {
            d[1] = 1;
        }
        //31717126241541717
        for (int i = 2; i < nums.length(); i++) {
            if (chars[i] == '0') {
                if (chars[i - 1] == '0' || chars[i - 1] > '2') {
                    return 0;
                }
                d[i] = d[i - 2];
            }
             else if (chars[i - 1] == '0') {
                d[i] = d[i - 1];
            } else if (chars[i - 1] == '1') {
                d[i] = d[i - 1] + d[i - 2];
            } else if (chars[i - 1] == '2') {
                if (chars[i] <= '6') {
                    d[i] = d[i - 1] + d[i - 2];
                } else {
                    d[i] = d[i - 1];
                }
            } else {
                d[i] = d[i - 1];
            }
        }
        return d[nums.length() - 1];
    }
}